The term "method" has a commonly understood meaning within the field of object-oriented computer program development and another, albeit different meaning, in the field of patent law. To avoid confusion, the following description will use the term "method" as typically understood within the field of object-oriented computer programming. The term "process" will be used as an expression of a "method of doing something." That is, in the sense of performing a series of operations that comprise a patentable "process."
As shown in FIG. 1 a typical computer (or computer system) 100 is comprised of a processor 105 device, memory 110 (often referred to as random access memory or RAM), one or more long-term storage devices 115 (such as, for example, magnetic hard and floppy disks, magnetic tape units, and optical disk storage), a display unit 120, and an input device such as, for example, a keyboard 125. As would be known to those of ordinary skill, long-term storage devices 115 are used to store programs 130 that are loaded into memory 110 prior to the program's execution by the processor 105. One illustrative program 130 is a compiler program.
Consider the source-code program fragment in FIG. 2. During compilation, an object-oriented "OBJECTIVE-C" compiler creates a class data structure for each declared class, in this example class A. As shown in FIG. 3, a typical class data structure 300 contains a pointer to a method name list 305, a pointer to a class cache data structure 310, and other data 315 such as, for example, class ISA and superclass pointers, and other standard information. The method name list 305 is itself comprised of one or more elements (320 and 325), one for each method defined for the class, where each element comprises method and parameter typing information 330, a pointer to the method's name string or method selector 335, and a pointer to the method's executable code segment 340. The class data structure 300 contains all the information necessary for a compiler to generate a series of instructions to implement dynamic method invocation.
As would be known to those of ordinary skill in the art of object-oriented compiler design, class cache data structures, accessed via the class data structure's 300 class cache pointer 310, are used at program run-time to speed the execution of dynamic method invocation. Class cache data structures are updated during program execution.
Referring again to the source-code fragment shown in FIG. 2, when the compiler parses the method call a x!, it generates executable instructions to perform the following operations:
Step 1: Load a pointer to the instance of the object `a` into a first specified register of the processor executing the program (the value `a` represents an object type identifier). PA1 Step 2: Load a pointer to the method name string "x" into a second specified register. PA1 Step 3: Generate an instruction to call the standard MessageSend dispatch function. As would be known to those of ordinary skill, the MessageSend function is responsible, at program execution time, for locating the executable code segment 340 associated with the method being called. (The pointer value loaded in step 1 is MessageSend's first parameter and the pointer value loaded in step 2 is MessageSend's second parameter.) PA1 Step 3a: Load the address of the class data structure associated with the instance whose address is in the first specified register; the address of class A's class data structure 300. (By convention, if the value in the first specified register is nil MessageSend returns nil and the following operations are not performed.) PA1 Step 3b: Load the address of the class cache associated with the class data structure; the address of class A's class cache 310. PA1 Step 3c: Search the class cache identified in step 3b for the method name string whose address is loaded in the second specified register (see step 2 above). If a match between the method name string and an entry in the class cache is not found, the current class's class data structure is searched and then the current class's parent class data structure is searched. Each class data structure in a method call's inheritance chain is searched as needed in this manner. If no match is found, a run-time error is generated. If a match is found, the current class cache data structure is updated and processing continues to step 3d. PA1 Step 3d: Jump to the executable code segment found in step 3c.
At program run-time, a copy of the executable file (comprised of linked object-code modules) is loaded into memory 110 and a string unification operation is performed to resolve/unify multiple pointers to common method name strings. (This is important when an executable file is comprised of multiple object code modules.) Following initialization, instructions generated by the compiler are processed/executed by the processor 105.
When the instruction to call the MessageSend dispatch function (described above in step 3) is executed, the following sequence of steps are performed:
As described above the MessageSend, or a functionally equivalent dispatch function, treats all method call operations as dynamic invocations. That is, the address of the target executable code (for example, the code to implement method `x`) is computed at run-time through a general search procedure. Even though class caches (typically implemented as hash tables) are used to speed this operation, conventional MessageSend functions require a number of pointer/address comparisons and searches through, possibly, a number of different class data structures.
While dynamic method invocation provides a flexibility not found in many programming languages, the time required to provide this capability can be a significant factor in degrading a program's run-time performance. This is because, in practice, only a fraction of a program's method calls actually need to be treated in a dynamic manner. The invention is directed at a method dispatch technique which can improve a program's run-time performance by avoiding dynamic method invocation in those instances where it is not needed. While not limiting, the inventive technique is particularly useful at improving the run-time characteristics of a source-code program compiled using any one of the currently available "OBJECTIVE-C" compilers.